package Z.dailyExercise._0222;

public class _766托普利茨矩阵 {
    public static void main(String[] args) {
        int num = 1234;
        System.out.println(num>>1);
    }

    /**
     * 自解：从第一行开始的第i行 从第一个开始进行累计计算 得到的int 必须和上一行累计得到的int相等
     * 会因为数值超出范围判断不出来 只能便利
     * @param matrix
     * @return
     */
    public boolean isToeplitzMatrix(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;
        //第i行
        for(int i=1;i<m;i++){
            long addNum=0,addUp=0;
            for (int j=1;j<n;j++){
                addNum += matrix[i][j]*Math.pow(10,n-1-j);
                addUp +=matrix[i-1][j-1]*Math.pow(10,n-1-j);
            }
            if (addNum != addUp){
                return false;
            }
        }
        return true;
    }

    /**
     * 按照线深度优先便利
     * 以0，0开始的那个线作为分界线
     * @param matrix
     * @return
     */
    public boolean isToeplitzMatrix1(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        //分界线下方的线
        for (int i=0;i<m;i++){
            if (!dfs(matrix,i,0,matrix[i][0]) ) return false;

        }
        for (int j=0;j<n;j++){
            if (!dfs(matrix,0,j,matrix[0][j]) ) return false;

        }

        return true;





    }

    public boolean dfs(int[][] matrix,int i,int j,int initval){//i.j该条线的第一个节点
        //递归终止：边界
        if (i>=matrix.length || j>= matrix[0].length){
            return true;
        }
        if (matrix[i][j] != initval) return false;

        return dfs(matrix,i+1,j+1,initval);

    }
}
